1. Field of the Invention
The present invention relates generally to data traffic over a multi-hop network. More specifically, the present invention relates to managing admission and routing of data streams transmitted over a multi-hop 802.11 based network (or a similar network) that provides traffic-shaping and rate-adaptation services at each hop.
2. Discussion of the Related Art
A mechanism for both controlling admission and making routing decisions is a desirable tool for efficient network management. In a 802.11 network, such a mechanism determines for each new user which access point to associate with and which route, among the multiple potential routes, traffic and packets associated with the user should follow to reach their respective destinations. Such a mechanism may be driven, at least in part, by resource availability (e.g., bandwidth and the number of access points) and the users' Quality-of-Service (QoS) requirements (e.g., transmission rate, throughput, delay, and signal-to-noise ratio). A new user may be denied admission when the required resources are not available, or when user QoS requirements (for both the new user and existing users) would not be satisfied if the new user is admitted. For an interactive voice communication application (e.g., “voice over IP” or “VoIP”), the resource and QoS requirements may include transmission throughput, delay and packet loss. Thus, a desirable admission control policy ensures that the network can support a given number of users without violating the QoS constraints, or the limits of the system. In a multi-hop network, the admission control policy should also prevent bottlenecks, and therefore serves to limit the number of users that can be supported.
A number of admission control algorithms have been proposed for a single-hop wireless network. For example, the article “Channel quality dependent scheduling for flexible wireless resource control,” by Z. Jiang, L. Chang, and N. K. Shankaranarayanan, published in the Proceedings of IEEE Globecom 2001, discloses a method that optimizes only throughput. The article “Distributed multi-hop scheduling and medium access with delay and throughput constraints in mind,” by V. Kanodia, C. Li, A. Sabharwal, B. Sadeghi, and E. Knightly, published in Proceedings of ACM MobiCom 2001, discloses a method that optimizes both the throughput and the delay. For a 802.11-based multi-hop network, the article “Admission control for multihop wireless backhaul networks with QoS support” (“LNPWZ06”), by S. Lee, G. Narlikar, M. Pal, G. Wilfong, and L. Zhang, published in the Proceedings of IEEE WCNC 2006, Las Vegas Nev., April 2006, discloses a method that meets each user's QoS requirements in delays and connection rates.
Other admission control algorithms take into consideration other options, such as aggregation of voice packets at access-points in the scenario of a multi-hop network. Aggregation of voice packets is disclosed, for example, in the article “A Joint Traffic Shaping and Routing Approach to Improve the Performance of 802.11 Mesh Networks” (“WiOpt06”), by C. Pepin, U. Kozat, and S. A. Ramprashad, published in the Proceedings of WiOpt 2006, Apr. 3-7, 2006 and in the U.S. patent application “Method for Improving Capacity in Multi-Hop Wireless Mesh Networks” (“NPA06”), Ser. No. 11/531,384, by S. Ramprashad, C. Pepin, and U. Kozat.
Once a user is admitted into the network, a routing scheme of the system determines proper routing of the user's data packets to their destinations. Routing in a multi-hop wireless network has been extensively discussed in the literature. In earlier wireless routing protocols (e.g., AODV, DSR, DSDP, and TORA), routing is handled independently from the lower layers, with path discovery being performed in a best-effort fashion without regard for system performance or QoS. Such routing algorithms are intended mainly for Mobile Ad Hoc networks (MANETs), where finding a connected path has priority (see, e.g., http://www.ietf.org/html.charters/manet-charter.html).
It is important to note that such methods do not directly consider important issues at the lower layers. Specifically, if a network is such that there are high overheads in handling and transmitting packets at lower communication layers, as is the case of 802.11 networks, a routing protocol that does not take such overheads and lower layers into consideration can lead to poor system performance.
Taking QoS into consideration in path discovery is discussed, for example, in the article “A high-throughput path metric for multi-hop wireless routing,” D. S. J. De Couto, D. Aguayo, J. Bicket, and R. Morris, in Proceedings of ACM Mobicom 2003, San Diego Calif., September 2003. That article discusses a method that minimizes the expected total number of transmissions and retransmissions required to successfully deliver a packet. A new metric is devised which incorporates the effects of link loss ratios, asymmetry in the loss ratios in the two directions of each link, and interference among the successive links of a path. The metric is implemented in the DSDV and DSR routing protocols and is shown to provide better performance than a minimum hop-count metric, particularly for paths with two or more hops.
The prior art includes complex approaches that jointly route and schedule packets to satisfy user QoS requirements. Such approaches can be ineffective due to the complexity of the problem. For example, solving the joint scheduling and routing problem to satisfy required connection rates in a multi-hop wireless network is a known NP-complete problem. See, e.g., the LNPWZ06 article discussed above. The prior art approaches are also ineffective because they focus on only one or two parameters at a time (e.g., throughput and delay) for each user independently. Therefore, in general, the resulting solutions cannot easily scale with the increase in users or access points. In fact, as new users join the network, such approaches may even create bottlenecks.
Beyond such general approaches one may consider more carefully the applications being admitted into the system and by doing so be able to improve performance and simplify the optimization problem. For example, for voice applications (e.g., VoIP applications), or media applications in general that generate small packet sized data persistently, many benefits may be achieved using traffic-shaping at intermediate hops as shown in “WiOpt06” and “NPA06”. In such a scenario one can directly consider important issues at lower layers such as the Medium Access Control (MAC) and Physical (PHY) layers. Specifically, by carefully selecting lower-layer mechanism such as aggregation and bursting levels at each hop one can reduce the inherent inefficiencies under the 802.11 protocol for voice or similar traffic. With this the number of VoIP calls that may be supported by such a system may increase substantially. Admission and routing control in such a scenario should take into account such lower layer mechanisms.